package com.ctrip.study.algorithm.pratice;

import org.junit.Test;

import com.ctrip.study.algorithm.pratice.CalcTreeMaxLength.Tree.TreeNode;

import junit.framework.TestCase;

/**
 * 求二叉树中节点的最大距离.
 */
public class CalcTreeMaxLength extends TestCase{
	
	 public static int maxLen = 0;
	
	@Test
	public void test(){
		Tree tree = getTree();
		getMaxTreeMaxLength(tree.root);
		assertEquals(5, maxLen);
	}

	private void getMaxTreeMaxLength(TreeNode root) {
		if(root == null){
			return;
		}
		if(root.left != null){
			getMaxTreeMaxLength(root.left);
			root.maxLeft = Math.max(root.left.maxLeft, root.left.maxRight) + 1;
		}
		if(root.right != null){
			getMaxTreeMaxLength(root.right);
			root.maxRight = Math.max(root.right.maxLeft, root.right.maxRight) + 1;
		}
		maxLen = Math.max(maxLen, root.maxLeft + root.maxRight - 1);
	}


	public Tree getTree() {
		Tree tree = new Tree();
		tree.insert(tree.new TreeNode(10));
		tree.insert(tree.new TreeNode(5));
		tree.insert(tree.new TreeNode(20));
		tree.insert(tree.new TreeNode(5));
		tree.insert(tree.new TreeNode(2));
		tree.insert(tree.new TreeNode(6));
		tree.insert(tree.new TreeNode(12));
		tree.insert(tree.new TreeNode(22));
		tree.insert(tree.new TreeNode(1));
		tree.insert(tree.new TreeNode(4));
		tree.insert(tree.new TreeNode(8));
		return tree;
	}
	
	public class Tree{
		
		public TreeNode root;
		
		public void insert(TreeNode node){
			if(root == null){
				root = node;
			}else{
				TreeNode currentNode = root;
				TreeNode parentNode = null;
				boolean isLeft = true;
				while(currentNode != null){
					parentNode = currentNode;
					if(node.key < currentNode.key){
						currentNode = currentNode.left;
						isLeft = true;
					}else{
						currentNode = currentNode.right;
						isLeft = false;
					}
				}
				if(isLeft){
					parentNode.left = node;
				}else{
					parentNode.right = node;
				}
			}
		}
		
		public class TreeNode{
			public int key;
			public TreeNode left;
			public TreeNode right;
			int maxLeft = 0;  
		    int maxRight = 0;
			
			public TreeNode(int key){
				this.key = key;
			}
			
			@Override
			public String toString() {
				return "TreeNode [key=" + key + "]";
			}
		}
		
	}

}
